package kyssion.leetcode.num151_200;

public class code188_买股票最佳时机4 {

    public static void main(String[] args) {

    }

    public int maxProfit(int k, int[] prices) {
        if (prices.length == 0) {
            return 0;
        }
        if(k>=prices.length/2){
            //交易次数不限制
            return maxProfit(prices);
        }
        int n = prices.length;
        int[] g = new int[n];
        int[] l = new int[n];
        for (int j = 1; j <= k; ++j) {
            int before = g[0];
            for (int i = 1; i < prices.length; ++i) {
                int diff = prices[i] - prices[i - 1];
                l[i] = Math.max(before +
                        Math.max(diff, 0), l[i - 1] + diff);
                before = g[i];
                g[i] = Math.max(l[i], g[i - 1]);
            }

        }
        return g[n - 1];
    }
    private int maxProfit(int[] prices){
        int n=prices.length;
        if (n==0||n==1){
            return 0;
        }
        int res=0;
        for (int i = 1; i <n ; i++) {
            if (prices[i]>prices[i-1]){
                res+=prices[i]-prices[i-1];
            }
        }
        return res;
    }

    public int maxProfit2(int k, int[] prices) {
        if (prices.length == 0) {
            return 0;
        }
        int n = prices.length;
        int[][] g = new int[n][k + 1];
        int[][] l = new int[n][k + 1];
        for (int j = 1; j <= k; ++j) {
            for (int i = 1; i < prices.length; ++i) {
                int diff = prices[i] - prices[i - 1];
                l[i][j] = Math.max(g[i - 1][j - 1] +
                        Math.max(diff, 0), l[i - 1][j] + diff);
                g[i][j] = Math.max(l[i][j], g[i - 1][j]);
            }
        }
        return g[n - 1][k];
    }
}
